// ECE556 - Copyright 2013 University of Wisconsin-Madison.  All Rights Reserved.

#include "ece556.h"
#include "foo.h"
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#define LEN     60
#define EDGE_NUM (rst->gx)*(rst->gy - 1) + (rst->gy)*(rst->gx - 1)

routingInst *readBenchmark(const char *fileName)
{
 	routingInst *rst;
        if ( !(rst = (routingInst*)malloc(sizeof(routingInst))))
                exit (0);

        FILE            *fp = fopen (fileName, "r");
        char            line[LEN];

/*************************************************************** 
        rst is the variable to return in this function
****************************************************************/

        int             cap;            //      default capacity
        int             num_net;        //      num net
        int             num_blk = 0;        //      blockage
        int             cnt_net = 0;
        int             cnt_pin = 0;
        int             num_pin = 0;

        point           *node = NULL;

        char    str[LEN];
        while ( fgets (line, LEN, fp) )
        {
                //      read file head
                if (sscanf ( line, "grid\t%d %d", &(rst->gx), &(rst->gy) ))
                {
                        if (!(node = (point*)calloc((rst->gx)*(rst->gy), sizeof(point))))
                                exit (0);
                        int     i, j;
                        for ( i=0; i < rst->gx; ++i )
                                for ( j=0; j < rst->gy; ++j )
                                        assign_point ( node+j+(rst->gy)*i, i, j );
                        if ( !(rst->edgeCaps = (int*)calloc(EDGE_NUM, sizeof(int))))
                                exit (0);
                        if ( !(rst->edgeUtils = (int*)calloc(EDGE_NUM, sizeof(int))))
                                exit (0);
                        if ( !(rst->edgeWeights = (float*)calloc(EDGE_NUM, sizeof(int))))
                                exit (0);
                        continue;
                }       //      gx,gy
                if (sscanf ( line, "capacity\t%d", &cap ))
                {
                        for ( int i = 0; i < EDGE_NUM; ++i )
                        {
                                rst->edgeCaps[i] = cap;
                                rst->edgeUtils[i] = 0;
                        }
                        continue;
                }       //      default capacity
                if (sscanf ( line, "num net %d", &num_net ))
                {
                        if (!(rst->nets = (net*)calloc(num_net, sizeof(net))))
                                exit (0);
                        cnt_net = -1; 
                        continue;
                }       //      num_net
                //      read net information
                if ( !strncmp (line, "n", 1) )
                {
                        ++ cnt_net;
                        char    *first_space = strchr ( line, ' ' );
                        strncpy ( str, first_space+1, LEN );
                        num_pin = atoi (str);
                        rst->nets[cnt_net].id = cnt_net; 
                        rst->nets[cnt_net].numPins = num_pin;
                        if (!(rst->nets[cnt_net].pins = (point*)calloc (num_pin, sizeof(point))))
                                exit (0);
//                        if (!(rst->nets[cnt_net].edgeUtils = (int*)calloc(rst->numEdges,sizeof(int))))
//                                exit (0);
                        cnt_pin = 0;
                        continue;
                }
                /* still reading pin info*/
                if ( (cnt_net < num_net) && (cnt_pin < num_pin) )
                {
                        int     x, y;
                        sscanf (line, "%d %d\n", &x, &y);
                        rst->nets[cnt_net].pins[cnt_pin].x = x;
                        rst->nets[cnt_net].pins[cnt_pin].y = y;
                        ++ cnt_pin;
                        if (cnt_pin == num_pin)         /* finish all pins for a single net */
                        {
//                                find_bb ( rst->nets[cnt_net] ); /* bounding box */
                        }
                        continue;
                }
                if ( !num_blk )
                {
                        num_blk = atoi (line);
                        continue;
                }
                //      read blk info
                int     x1, y1, x2, y2, c;
                sscanf (line, "%d %d %d %d %d", &x1,&y1,&x2,&y2,&c);
                int     edge_id = find_edge_id (x1, y1, x2, y2, rst);
                if ( edge_id == -1 )
                        exit (0); 
                rst->edgeCaps[edge_id] = c;
        }
        rst->cap = cap;
        rst->numNets = num_net;
        rst->numEdges = EDGE_NUM;
        rst->netWeights = new_float_array (rst->numNets);
        rst->edgeUtils = new_array (EDGE_NUM);
        rst->edgeWeights = new_float_array (EDGE_NUM);

/* 
 *      Print out of reading benchmark
 */
        printf ( "\nReading Benchmark :\n\n" );
        printf ( "\tGrid dimension :\t%d X %d\n", rst->gx, rst->gy );
        printf ( "\tEdge number :\t\t%d\n", rst->numEdges );
        printf ( "\tNet number :\t\t%d\n", rst->numNets );
        printf ( "\tDefault capacity :\t%d\n", cap );
        printf ( "\tBlockage number :\t%d\n", num_blk );
        
        return  rst;
}
int solveRouting(routingInst *rst)
{
        clock_t begin, end;
        double  time_spent;
        begin = clock();

/*************************************************************** 
        initial solution : generate MST for each of nets
****************************************************************/ 
        for (int i=0; i < rst->numNets; i++)
                gen_mst ( rst->nets+i, rst );
        printf ( "\nInitial Routing :\n\n");
        printf ( "\tTotal wirelength :\t%d\n", tot(rst) );
        printf ( "\tTotal overflow :\t%d\n", ofl (rst) );
        cal_netWeights ( rst );

/*************************************************************** 
        improving solution : rip-up and reroute
****************************************************************/ 
        int     *sort = sort_array ( rst->netWeights, rst->numNets );
        printf ( "\n\nRRR : \nthis may take some time for some reason ... don't worry man\n" );

        int     size = 1000;
        for ( int i = 0; i < 200; i++ )         // take 108s to decrease to 506K(200)
        {
                printf ( "%8d\t%8d\t%8d\t%.4f\n", i, ofl(rst), sort[i], rst->netWeights[sort[i]] );
                rip_up ( sort[i % size], rst );
                reroute ( sort[i % size], rst );
//                printf ( "%d\tTotal overflow :\t%d\n",i, ofl (rst) );
                if ( !(i+1)%size )
                        sort = sort_array ( rst->netWeights, rst->numNets );
        }

        end = clock();
        time_spent = (double)(end-begin)/CLOCKS_PER_SEC;
        printf ( "running time : %.2f\n", time_spent );
        return  1;
}


int writeOutput(const char *outRouteFile, routingInst *rst)
{
  /*********** TO BE FILLED BY YOU **********/
        FILE *fp = fopen ( outRouteFile, "w" );
        print_result ( fp , rst );
        return 1;
}

int release(routingInst *rst)
{
  /*********** TO BE FILLED BY YOU **********/
        free ( rst );
  return 1;
}
